package com.leetcode.algorithm.y19.m04;

import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;
import com.leetcode.algorithm.common.TreeNodeExt;

/**
 * leetcode-cn.com
 * 
 * (done)414. 第三大的数
 * (done)215. 数组中的第K个最大元素
 * (done)671. 二叉树中第二小的节点
 * (done)230. 二叉搜索树中第K小的元素
 * @author: jie.deng
 * @time: 2019年4月8日 下午7:36:46
 */
public class MySolution0408 {
    
    /**
     * 414. 第三大的数
     * 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
     * 
     * 示例 1:
     * 输入: [3, 2, 1]
     * 输出: 1
     * 解释: 第三大的数是 1. 
     * 
     * 示例 2:
     * 输入: [1, 2]
     * 输出: 2
     * 解释: 第三大的数不存在, 所以返回最大的数 2 . 
     * 
     * 示例 3:
     * 输入: [2, 2, 3, 1]
     * 输出: 1
     * 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。
     * 
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        int i1 = nums[0];
        Integer i2 = null;
        Integer i3 = null;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > i1) {
                i3 = i2;
                i2 = i1;
                i1 = nums[i];
            } else if (nums[i] == i1) {
                continue;
            } else {
                if (i2 == null) {
                    i2 = nums[i];
                } else {
                    if (nums[i] > i2) {
                        i3 = i2;
                        i2 = nums[i];
                    } else if (nums[i] == i2) {
                        continue;
                    } else {
                        if (i3 == null || nums[i] > i3) {
                            i3 = nums[i];
                        }
                    }
                }
            }
        }
        return i3 == null ? i1 : i3;
    }
    
    /**
     * 215. 数组中的第K个最大元素
     * 
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * 
     * 示例 1:
     * 
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 示例 2:
     * 
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     * 说明:
     * 
     * 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        KthLargest kthLargest = new KthLargest(k, nums);
        return kthLargest.searchKthLargest(k);
    }
    
    /**
     * 671. 二叉树中第二小的节点
     * 
     * 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 
     * 
     * 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
     * 
     * 示例 1:
     * 
     * 输入: 
     *     2
     *    / \
     *   2   5
     *      / \
     *     5   7
     * 
     * 输出: 5
     * 说明: 最小的值是 2 ，第二小的值是 5 。
     * 示例 2:
     * 
     * 输入: 
     *     2
     *    / \
     *   2   2
     * 
     * 输出: -1
     * 说明: 最小的值是 2, 但是不存在第二小的值。
     * @param root
     * @return
     */
    public int findSecondMinimumValue(TreeNode root) {
        return findSecondMinimumValue(root, root.val);
    }
    
    private int findSecondMinimumValue(TreeNode root, int val) {
        if (root == null) {
            return -1;
        }
        if (root.val != val) {
            return root.val;
        }
        int secondMinimumValueL = findSecondMinimumValue(root.left, val);
        int secondMinimumValueR = findSecondMinimumValue(root.right, val);
        if (secondMinimumValueL == -1 || secondMinimumValueR == -1) {
            return secondMinimumValueL ^ -1 ^ secondMinimumValueR;
        } else {
            return Math.min(secondMinimumValueL, secondMinimumValueR);
        }
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     * 
     * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
     * 
     * 说明：
     * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
     * 
     * 示例 1:
     * 
     * 输入: root = [3,1,4,null,2], k = 1
     *    3
     *   / \
     *  1   4
     *   \
     *    2
     * 输出: 1
     * 示例 2:
     * 
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 3
     * 进阶：
     * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            if (!stack.isEmpty()) {
                cur = stack.pop();
                k--;
                if (k == 0) {
                    return cur.val;
                }
                cur = cur.right;
            }
        }
        return -1;
    }
    public int kthSmallestOnline(TreeNode root, int k) {
        TreeNodeExt tree = new TreeNodeExt(root);
        // 后续遍历，填充以当前结点为根的树的结点个数
        TreeNodeExt pre = null; // 划重点:记录上次遍历的结点
        Stack<TreeNodeExt> stack = new Stack<TreeNodeExt>();
        stack.push(tree);
        while (!stack.isEmpty()) {
            TreeNodeExt cur = stack.peek(); // 先判断下孩子结点是否遍历完成
            if ((cur.left == null && cur.right == null) || ((cur.right == null ? cur.left : cur.right) == pre)) {
                // 划重点:如果当前结点没有孩子或者上次遍历的结点为左孩子(没有右孩子的情况)或者右孩子，则遍历当前结点
                stack.pop();
                int i1 = 1;
                i1 += cur.left == null ? 0 : cur.left.i1;
                i1 += cur.right == null ? 0 : cur.right.i1;
                cur.i1 = i1;
                pre = cur;
            } else {
                // 需要先遍历孩子结点，孩子入栈
                // 入栈顺序为先右孩子后左孩子，以确保出栈时的顺序是先左后右
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
        
        pre = tree;
        TreeNodeExt cur = null;
        while (k > 0) {
            cur = pre.left;
            while (cur != null && cur.i1 >= k) {
                pre = cur;
                cur = pre.left;
            }
            if (cur != null) {
                k -= cur.i1; // 左子树
            }
            k -= 1; // 当前结点
            if (k >= 1) {
                pre = pre.right; // 右子树
            }
        }
        return pre.val;
    }
    
}
